Spatial data structures typically assign a location representation, or location code, to each data object in a computer program. Structured spatial data structures often use integer location codes which encode location information in such a way that discrete integer operations on these location codes can replace (or act as approximate surrogates for) more computationally expensive operations on traditional floating-point location representations, such as real-number coordinate pairs on the two-dimensional plane, or geographic coordinates on a spheroid. Structured spatial data structures have been used for many common spatial data applications, including indexing spatial databases, representing vector and raster data, and graph data structures.
By far the most widely studied and commonly used structured spatial data structure is the square quadtree. The quadtree can be defined in a number of equivalent ways. A high resolution grid of square cells can be recursively aggregated in groups of 4 squares to form successively coarser resolution cells. Conversely, a coarse resolution base cell can be recursively subdivided into 4 smaller child squares. A hierarchical quadtree indexing can be formed by assigning a base address to each coarse base cell, and forming the address of child (and descendent) cells by concatenating one of the additional digits 1-4 to the parent cell index, where the digits are chosen in a geometrically consistent fashion. The resulting indices can be arithmetically and algebraically manipulated to provide efficient versions of important operations such as vector addition and metric distance.
Structured spatial data structures based on hexagonal cells can be superior to square grids under many comparison metrics. For example, planar hexagonal grids are the most efficient location quantizer, have the best angular resolution, and the cells display uniform neighbor adjacency. Further, a discrete metric distance on a hexagonal grid is a better approximation to distance on the real number plane, enabling more efficient coarse filtering of spatial proximity queries. But unlike the square quadtree which can be defined equivalently via aggregation or recursive partition, multiple resolutions of hexagonal cells cannot be created by simple aggregation of atomic pixels, nor by recursive partition.
Additional background information relating to modified generalized balanced ternary (MGBT), aperture three hexagon trees (A3HT), and hierarchical location coding methods for geospatial computing on icosahedral aperture 3 hexagon discrete global grid systems (DGGS), can be found in U.S. patent application Ser. No. 11/038,484, filed Jan. 21, 2005, and U.S. patent application Ser. No. 12/897,612, filed Oct. 4, 2010, both of which are incorporated by reference herein in their entireties.